Thực đơn
Đống_(cấu_trúc_dữ_liệu)
Bảng sau đây thống kê độ phức tạp tính toán của các thao tác trên đống. Tất cả các mục đều là thời gian xấu nhất ngoại trừ các mục được đánh dấu sao là thời gian trả dần. Tên hàm được đặt theo đống-max.
| Thao tác | Nhị phân[1] | Nhị thức[1] | Fibonacci[1] | Ghép[4] |
|---|---|---|---|---|
| tìm-max | O ( 1 ) {\displaystyle O(1)} | O ( 1 ) {\displaystyle O(1)} | O ( 1 ) {\displaystyle O(1)} | O ( 1 ) {\displaystyle O(1)} [cần dẫn nguồn] |
| xóa-max | O ( log n ) {\displaystyle O(\log n)} | O ( log n ) {\displaystyle O(\log n)} | O ( log n ) {\displaystyle O(\log n)} * | O ( log n ) {\displaystyle O(\log n)} * |
| chèn | O ( log n ) {\displaystyle O(\log n)} | O ( log n ) {\displaystyle O(\log n)} | O ( 1 ) {\displaystyle O(1)} | O ( 1 ) {\displaystyle O(1)} *[cần dẫn nguồn] |
| tăng-khóa | O ( log n ) {\displaystyle O(\log n)} | O ( log n ) {\displaystyle O(\log n)} | O ( 1 ) {\displaystyle O(1)} * | O ( log n ) {\displaystyle O(\log n)} * |
| hợp | O ( n ) {\displaystyle O(n)} | O ( log n ) {\displaystyle O(\log n)} ** | O ( 1 ) {\displaystyle O(1)} | O ( 1 ) {\displaystyle O(1)} * |
(*)Thời gian trả dần
(**)n là kích thước của đống lớn hơn
Thực đơn
Đống_(cấu_trúc_dữ_liệu)Liên quan
Tài liệu tham khảo
WikiPedia: Đống_(cấu_trúc_dữ_liệu)